class Solution(object):
    def wordBreak(self, s, wordDict):
        all_path, results = [], []

        def divide_word(s, path):
            if len(s) == 0:
                all_path.append(path[:])
                return
            
            for i in range(len(s)):
                prefix = s[:i+1]
                if prefix in wordDict:
                    path.append(prefix)
                    divide_word(s[i+1:], path)
                    path.pop()
        
        divide_word(s, [])

        for div_word in all_path:
            results.append(' '.join(div_word))

        return results

    
str = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
print(Solution().wordBreak(str, wordDict))
